public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

来源：百度知道 编辑：UC知道 时间：2024/07/07 19:35:28
使用二进制搜索算法来搜索指定列表，以获得指定对象。在进行此调用之前，必须根据指定的比较器（通过上面的 Sort(List, Comparator) 方法）对列表进行升序排序。如果没有对列表进行排序，则结果是不明确的。如果列表包含多个等于指定对象的元素，则无法保证找到的是哪一个。
此方法对“随机访问”的列表运行 log(n) 次（这提供了一个接近固定时间的位置访问）。如果指定列表没有实现 RandomAccess 接口并且是一个大型列表，则此方法将执行基于迭代器的二进制搜索，执行 O(n) 次链接遍历和 O(log n) 次元素比较。

返回：
如果搜索键包含在列表中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。插入点 被定义为将键插入列表的那一点：即第一个大于此键的元素索引，如果列表中的所有元素都小于指定的键，则为 list.size()。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Searching {
public static void main(String[] args) {
String[] strings = { "0", "1", "2", "3", "4", "5"};

List<Integer> integers = new ArrayList<Integer>();
for(String s : strings){
integers.add(Integer.valueOf(s));
}
if(integers.get

问题1，2其实可以一起讲，就是：你没完全理解==，equals和自动装箱（auto boxing)。仔细看你的comparator的实现return i<j?-1:(i==j?0:1);这句话，注意，你的参数是Integer类型，不是基本类型int，你对类的对象做==操作，是比较它们是否是同一个引用，而不是他们的值是否相等。所以，你用这个比较器做二叉搜索，结果肯定是不可预知的。当<判断失败的时候，后面的==基本不可能是true，这也是为什么if(integers.get(1)==new Integer(1)){System.out.println("<3>");}这句话不能打印出<3>来。你后面那个实现是正确的，因为类的对象没有<操作和>操作，所以编译器会把Integer对象自动转成int再执行比较。

问题3：api写的很清楚，当找不到的时候，会返回【-（插入值）-1】，在这个程序里，因为你的比较器写的不对，所以搜索失败，并且它认为插入值是1，这没有问题啊。其实，因为上面说的问题，他返回任何奇奇怪怪的数都有可能。

如果你想对两个Integer类的对象比较值，你可以调用i.eqauls(j);或者i.intValue()==j.intValue();intValue方法返回的是Integer对象包装的基本类型的int值

另外，补充一点，不知道是你描述的不好，还是我理解的不对。你说的“根据API文档解释， Comparator只是在search之前对list进行排序。”不对，binarysearch不会排序，而是api要求你在调用binarySearch之前，必须保证传进去的list是已排序了的，你可以调用Collections.sort来实现，也可以自己写排序算法
=========================================================
comparator的作用就是比较器啊，告诉排序方法怎样比较两个值谁大谁小或相等，对于Integer，当然比较规则很直观，但是对别的类呢，比如你有一个一个Student类，你希望根据学号来排序，查找，你就需要定义自己的Comparat